/**
 * @author: tengjuyuan
 * @file: insertionSort.h
 * 插入排序
 */
#include <vector>
using namespace std;

// 对于简单的数据类型排序，升序排列
template <typename T>
void insertionSort(vector<T> & a)
{
    // for (size_t i = 0; i < a.size(); i++)
    // {
    //     for (size_t j = 0; j < i; j++)
    //     {
    //         if (a[i] < a[j])
    //         {
    //             T temp = a[i];
    //             a[i] = a[j];
    //             a[j] = temp;
    //         }
    //     } 
    // }
    
    int j;
    for (int p = 1; p < a.size(); p++)
    {
        T tmp = a[p];
        for (j = p; j > 0 && tmp < a[j - 1]; j--)
        {
            a[j] = a[j - 1];
        }
        a[j] = tmp;
    }
}




// 最完整的STL排序算法，模版包括迭代器，比较器，和数据类型
// 将Ojbect类型作为第四个参数，仅仅是为了增加一个辅助的泛型类型
template <typename Iterator, typename Comparator, typename Object>
void insertionSort(const Iterator & begin, const Iterator & end,
                    Comparator lessThan, const Object& obj)
{
    Iterator j;
    for (Iterator p = begin + 1; p != end; p++)
    {
        Object tmp = *p;
        for (j = p; j != begin && lessThan(tmp, *(j - 1)); --j)
        {
            *j = *(j - 1);
        }
        *j = tmp;
        
    }
    
}

// 模版包括迭代器，比较器
template <typename Iterator, typename Comparator>
void insertionSort(const Iterator& begin, const Iterator & end,
                    Comparator lessThan)
{
    if (begin != end)
    {
        insertionSort(begin, end, lessThan, *begin);
    }
    
}

// 模版包括迭代器和数据类型，升序排列
template <typename Iterator, typename Object>
void insertionSortHelp(const Iterator & begin, const Iterator & end,
                        const Object & obj)
{
    insertionSort(begin, end, less<Object>());
}

// 模版包含了迭代器
template <typename Iterator>
void insertionSort(const Iterator & begin, const Iterator & end)
{
    if(begin != end)
    {
        insertionSortHelp(begin, end, *begin);
    }
}
